package com.LeetCode.dp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三角形最小路径和
 */
public class SmallestPathInTriangle {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int m = triangle.get(triangle.size() - 1).size();
        int[]dp = new int[m];

        for(int i = 0; i<m; i++){
            dp[i] = triangle.get(n-1).get(i);
        }

        for(int i = n-2; i>=0 ;i--){
            for(int j = 0; j <= i; j++){
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j] , dp[j+1]);
            }
        }
        return dp[0];
    }

    @Test
    public void test(){
        List<List<Integer>> triangle = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(2));
        ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(3,4));
        ArrayList<Integer> list3 = new ArrayList<>(Arrays.asList(6,5,7));
        ArrayList<Integer> list4 = new ArrayList<>(Arrays.asList(4,1,8,3));
        triangle.add(list1);triangle.add(list2);triangle.add(list3);triangle.add(list4);
        System.out.println(minimumTotal(triangle));
    }
}
